Cite this Article
Wang Guo-Qiang, Luo He, Hu Xiao-Xuan. Generation of optimal persistent formations for heterogeneous multi-agent systems with a leader constraint. Chinese Physics B, 2018, 27(2): 028901  
Permissions
Generation of optimal persistent formations for heterogeneous multi-agent systems with a leader constraint
Wang Guo-Qiang1, 2, Luo He1, 2, †, Hu Xiao-Xuan1, 2
School of Management, Hefei University of Technology, Hefei 230009, China
Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei 230009, China

 

† Corresponding author. E-mail: luohe@hfut.edu.cn

Abstract

In this study, we consider the generation of optimal persistent formations for heterogeneous multi-agent systems, with the leader constraint that only specific agents can act as leaders. We analyze three modes to control the optimal persistent formations in two-dimensional space, thereby establishing a model for their constrained generation. Then, we propose an algorithm for generating the optimal persistent formation for heterogeneous multi-agent systems with a leader constraint (LC-HMAS-OPFGA), which is the exact solution algorithm of the model, and we theoretically prove its validity. This algorithm includes two kernel sub-algorithms, which are optimal persistent graph generating algorithm based on a minimum cost arborescence and the shortest path (MCA-SP-OPGGA), and the optimal persistent graph adjusting algorithm based on the shortest path (SP-OPGAA). Under a given agent formation shape and leader constraint, LC-HMAS-OPFGA first generates the network topology and its optimal rigid graph corresponding to this formation shape. Then, LC-HMAS-OPFGA uses MCA-SP-OPGGA to direct the optimal rigid graph to generate the optimal persistent graph. Finally, LC-HMAS-OPFGA uses SP-OPGAA to adjust the optimal persistent graph until it satisfies the leader constraint. We also demonstrate the algorithm, LC-HMAS-OPFGA, with an example and verify its effectiveness.

PACS: 89.20.Ff;87.85.St;89.65.Ef;02.30.Em
Keyword:leader constraint;heterogeneous multi-agent system;optimal persistent formation;minimum cost arborescence
1. Introduction

In recent years, the formation control of multi-agent systems (MAS) has become an important topic, and has found their wide applications in both military and civilian domains. There are many types of agents in MAS, such as mobile robots,[1] satellites,[2] unmanned aerial vehicles (UAVs),[3] and autonomous underwater vehicles (AUVs).[4] The main idea of MAS formation control is that several agents exchange information via communication links and use preset formation control methods to determine their movement, thereby forming and maintaining a specific formation shape.

At present, the set of communication links used by agents to maintain their formation shape can be expressed in multiple manners, including communication topology,[5,6] information exchange topology,[7] connection topology,[8] information structure,[9–11] and information topology.[12,13] In the present study, these links are referred to as communication topology, while the set of all the available communication links between agents are termed network topology. Both communication topology and network topology can be expressed by a weighted directed graph, which, hereafter, is named the directed graph. Furthermore, the communication topology of the agent formation is a subgraph of its network topology, where nodes denote the agents in the formation, arcs represent the communication links between agents, and the weight of each arc refers to the communication cost of the link.

The formation control approaches that an agent formation can be used to maintain its formation shape include the leader–follower-based approach, the virtual structure-based approach, the behavior-based approach, the consensus-based approach, the minimally rigid graph-based approach, and the minimally persistent graph-based approach. The minimally persistent graph-based approach is a formation control method based on distance, with the corresponding agent formation referred to as the minimally persistent formation.[14] The communication topology of the minimally persistent formation must be a minimally persistent graph in its network topology to minimize the number of communication links used by the agent formation to maintain its formation shape. In two-dimensional (2D) space, there must be and only arcs in a minimally persistent graph with nodes, and the in-degree of each node is less than or equal to 2.[9] Moreover, each agent must maintain a constant distance from the agents which have an outgoing arc to it in the communication topology during the movement of the minimally persistent formation. For the generation of minimally persistent formations, a graph operation method to transform from one minimally persistent formation to another minimally persistent formation was proposed.[9] In addition, an algorithm based on the Pebble game and its graph operations to generate minimally persistent formations was proposed.[15] Another algorithm applicable to the generation of minimally persistent formations with a circular structure was proposed.[16]

However, the minimally persistent formation of a given network topology is not unique. The minimally persistent formation with the smallest sum of the costs of the communication links in its communication topology is called the optimal persistent formation.[17] The communication topology of the optimal persistent formation must be an optimal persistent graph of its network topology. For the generation of optimal persistent formations, an algorithm suitable for optimal persistent formations with special structures, and based on the optimal rigid graph and the configuration of the triangle with a leader was proposed.[17] An optimal persistent formation generation algorithm, which is based on the optimal rigid graph and the operation of directed vertex addition and applicable to optimal persistent formations with triangles or quadrangles used as the basic structures, was proposed.[18] Another optimal persistent formation generation algorithm based on the optimal rigid graph with four directed operations was proposed,[19] which is suitable for optimal persistent formations with any structure.

For homogeneous agent formations, where each agent can act as a leader, the optimal persistent formation can be generated by simply directing the optimal rigid graph to one arbitrary optimal persistent graph. However, for a heterogeneous agent formation, only specific agents can act as the leader, and this leader constraint must be considered when directing the optimal rigid graph to the optimal persistent graph. To solve this problem, in this study are introduced the following innovations: (i) we propose the algorithm MCA-SP-OPGGA, which directs any optimal rigid graph to obtain an optimal persistent graph and we then prove the validity of this algorithm; (ii) we propose the algorithm SP-OPGAA, which adjusts any optimal persistent graph to satisfy the leader constraint and we then prove this algorithm validity; and (iii) we propose the algorithm LC-HMAS-OPFGA based on MCA-SP-OPGGA and SP-OPGAA, which generates the optimal persistent formation for heterogeneous multi-agent system with the leader constraint.

The rest of this study is organized in the following manner. In section 2, we analyze the problem and establish the model that describes it. In section 3, we propose an exact solution algorithm to solve the stated problem and prove its validity. In section 4, we illustrate this algorithm by a simulation example and verify the validity of the algorithm. In section 5, we draw some conclusions from this study and point out future directions of research in this field.

2. Problem analysis and modeling
2.1. Formation shape of agent formation

The represents the set of n agents, where the agents that can act as the leaders are represented by , with . Matrix represents the formation shape constituted by n agents as shown in Eq. (1) below.

In the above expression, F denotes the formation reference point (which is the position of one specific agent in the formation shape) and represents the position coordinates of the i-th agent in the coordinate system, with F used as the origin. For example, figure 1 shows the formation shape composed of five agents in the two-dimensional (2D) space, with their positions numbered as {1,2,3,4,5}, respectively. Their relative positions in the space are shown in the left portion in Fig. 1. If position four is regarded as the origin, then the coordinates of all the positions are shown in the right portion in Fig. 1.

Fig. 1. (color online) Formation shape composed of five agents and its mathematical description.
2.2. Network topology and communication topology of optimal persistent formation

The network topology of the agent formation composed of n agents can be expressed by the directed graph , where denotes the set of nodes in the graph, node vi denotes , is the set of arcs in the graph, arc represents the communication link from vi to vj, is the set of arc weights in the graph, and arc weight, , denotes the cost of the communication link from vi to vj, which is equivalent to the communication distance from vi to vj in this study. For example, figure 2 shows the network topology of five agents to keep the formation shape shown in Fig. 1.

Fig. 2. (color online) Network topology of the agent formation composed of five agents.

The communication topology of the above agent formation for maintaining its formation shape can be expressed by the directed graph , , where T is a subgraph of . The function, , is the sum of the weights of all the arcs in T and denotes the total communication cost when the agent formation maintains its formation shape. It is called the formation communication cost and shown in Eq. (2) as follows:

For a minimally persistent formation, the communication topology T is a minimally persistent graph in its network topology D, and means that vi needs to send its own information to vj when the formation tries to keep its formation shape. Then vj can adjust its movement to keep a constant distance from vi. In other words, there is a distance constraint between vj and vi. The function d(j), the in-degree of vj, denotes the number of distance constraints of vj with other agents. For example, under the network topology shown in Fig. 2, the communication topology of a minimally persistent formation is shown in Fig. 3. The number of communication links is , the in-degree of each node is less than or equal to 2, and its formation communication cost is 5588.

Fig. 3. (color online) Communication topology of a minimally persistent formation composed of five agents.

Furthermore, under the same network topology, the minimally persistent formation with the smallest formation communication cost is defined as the optimal persistent formation. Figure 4 shows the communication topology of an optimal persistent formation, whose formation communication cost is the smallest in all possible minimally persistent formations under the network topology shown in Fig. 2.

Fig. 4. (color online) Communication topology of an optimal persistent formation composed of five agents.
2.3. Problem modeling

The optimal persistent formation can be determined by the following three control modes[20] in 2D space.

i) Leader-first-follower (LFF): An agent, as a leader, can move freely in 2D space (i.e., it has 2 degrees of freedom). Another agent, as the first follower, needs to maintain a constant distance from the leader during movement (i.e., it has 1 degree of freedom). Each of the remaining agents, as ordinary followers, must maintain a constant distance from any other two agents during the movement (i.e., it has no degree of freedom). In this control mode, the in-degrees of the nodes corresponding to the leader, the first follower, and the ordinary followers in the communication topology of the formation are 0, 1, and 2 respectively.

ii) Leader-remote-follower (LRF): An agent, as a leader, can move freely in 2D space (i.e., it has 2 degrees of freedom). Another agent, as the remote follower, needs to maintain a constant distance from an agent apart from the leader during movement (i.e., it has 1 degree of freedom). Each of the remaining agents, as ordinary followers, must maintain a constant distance from any other two agents during the movement (i.e., it has no degree of freedom). In this control mode, the in-degrees of the nodes corresponding to the leader, the remote follower, and the ordinary followers in the communication topology of the formation are 0, 1, and 2 respectively.

iii) Co-leader: Three agents act as the co-leaders, each of whom needs to maintain a constant distance from any other agent during motion (i.e., each co-leader has one degree of freedom). Each agent, other than co-leaders, as an ordinary follower should maintain a constant distance from any other two agents during movement (i.e., it has no degree of freedom). In this control mode, the in-degrees of corresponding nodes of the co-leaders and the ordinary followers in the communication topology of the formation are 1 and 2, respectively.

The leader constraint of the optimal persistent formation for heterogeneous multi-agent systems can be described in this way: among the agents that can act as the leaders, there is one and only one agent whose in-degree of its corresponding node in the communication topology is 0, or else there are three and only three agents whose in-degree of their corresponding nodes in the communication topology is 1.

In this study, the generation of the optimal persistent formation for heterogeneous multi-agent systems with the leader constraint is formulated as the following optimization problem.

Among , the set of the n heterogeneous agents, is the subset of agents that can act as the leaders. To make sure the n agents comprise the optimal persistent formation and keep the formation shape , an optimal persistent graph must be generated as the communication topology for this formation. This formation must minimize , the formation communication cost corresponding to this communication topology, and the optimal persistent graph, T, must satisfy the leader constraint, namely one of the following conditions:

1) ,

2) : , , , , .

3. Algorithm

We propose the algorithm LC-HMAS-OPFGA to address the model named above. This algorithm includes two kernel sub-algorithms. The first sub-algorithm, MCA-SP-OPGGA, is used to direct an optimal rigid graph to an optimal persistent graph, and the second sub-algorithm, SP-OPGAA, is used to adjust an optimal persistent graph until it satisfies the leader constraint. Given the formation shape and the set of agents that can act as the leaders, LC-HMAS-OPFGA can generate the optimal persistent formation for heterogeneous multi-agent system under the leader constraint.

3.1. Algorithm for the generation of optimal persistent graph

In this subsection, we propose an optimal persistent graph generating algorithm based on minimum cost arborescence (MCA)[21] and shortest path (SP),[22] referred to as MCA-SP-OPGGA. By adding a virtual node and virtual arcs, generating and combining minimum cost arborescence, adding arcs, and reversing paths, this algorithm can direct any optimal rigid graph to obtain an optimal persistent graph. The pseudo-codes of this algorithm are shown in Table 1.

Table 1. Pseudo-codes of MCA-SP-OPGGA.

We will also verify the feasibility of MCA-SP-OPGGA theoretically. By proving the existence of MCA, the combinatorial properties of MCA, and the characteristics of adding arcs and reversing paths, it is proven that MCA-SP-OPGGA can generate an optimal persistent graph that satisfies the judging criterion shown in Lemma 2.

3.2. Adjusting algorithm for optimal persistent graph to satisfy leader constraint

When the optimal persistent graph does not satisfy the leader constraint, the optimal persistent graph adjusting algorithm based on shortest path[22] (SP-OPGAA), proposed below, can solve this problem. The optimal persistent graph that satisfies the leader constraint can be obtained using a path reversal operation, whose pseudo-code is shown in Table 2.

Table 2. Pseudo-codes of SP-OPGAA.

The validity of SP-OPGAA will be proven theoretically.

For the paths satisfying Lemma 3, Theorem 5 proves that SP-OPGAA can produce the optimal persistent graph satisfying the leader constraint through several path reversal operations.

3.3. Algorithm for the generation of optimal persistent formation for heterogeneous multi-agent system under leader constraint

Based on MCA-SP-OPGGA, SP-OPGAA, and the optimal rigid graph generating algorithm, an optimal persistent formation generating algorithm for heterogeneous multi-agent systems under the leader constraint (LC-HMAS-OPFGA) is here proposed. It can generate the optimal persistent formation for any formation shape in 2D space under any leader constraint, and its pseudo-code is shown in Table 3.

Table 3. Pseudo-codes of LC-HMAS-OPFGA.
4. Calculation examples

Now, we assume that one heterogeneous multi-agent persistent formation consists of 16 agents, namely , also assume that the communication cost of links between agents equals the Euclidean distance between them. They need to form and maintain a formation shape as shown in Fig. 5.

Fig. 5. (color online) Formation shape composed of 16 agents and its mathematical description.

The agents’ positions in the formation shape are numbered as 1, 2, …,16, respectively. Their relative positions in space are shown in the left part in Fig. 5 and their coordinates are shown in the right part in Fig. 5. The leader constraint is .

The process of generating the optimal persistent formation for the above heterogeneous multi-agent system using LC-HMAS-OPFGA is described as follows. The optimal rigid graph, R, is calculated by the algorithm mentioned in Ref. [17], and shown in Fig. 6. Then, the optimal persistent graph, T, corresponding to the above optimal rigid graph, R, is generated by MCA-SP-OPGGA, with the concrete steps as follows.

Fig. 6. (color online) Optimal rigid graph R.

After the optimal rigid graph, R, is transformed into a directed graph DR, , and , the two minimum cost arborescence (shown in Figs. 7(a) and 7(b)), are obtained respectively with the assistance of the virtual node v0. Then, the directed graph, T, is obtained by combining the two directed graphs, after v0 has been deleted as shown in Fig. 7(c).

Fig. 7. (color online) Process for MCA-SP-OPGGA to generate the optimal persistent graph, T. (a) The first minimum cost arborescence, and (b) the second minimum cost arborescence, , (c) directed graph, T, obtained by the combination of T1 and T2, (d) directed graph, T, after arc has been added, (e) directed graph, T, after the path, , has been reversed from v5 to v15, (f) directed graph, T, after arc a39 has been added; (g) directed graph, T, after path, , has been reversed from v2 to v9.

However, neither of and , the two arcs corresponding to the edge, , in the optimal rigid graph, R, is in T, and the in-degrees of both v8 and v15 are both 2. Therefore, the operation of adding arcs is carried out. Arc, , is added to T as shown in Fig. 7(d), then the node, v5, with an in-degree less than 2 is found and all the arcs on the path from v5 to v15 are reversed, so that the in-degrees of all nodes are less than or equal to 2. The directed graph, T, obtained is shown in Fig. 7(e). Similarly, arc a39 is added to the directed graph T, and then all the arcs on the path from v2 to v9 are reversed to gain the directed graph T as shown in Figs. 7(f) and 7(g). As a result, the in-degrees of all nodes in the directed graph, T, are less than or equal to 2, and both the number of all the arcs in T and that of all the edges in the optimal rigid graph, R, are 29, which meets the conditions of an optimal persistent graph as stated in Lemma 2. Therefore, T is an optimal persistent graph of R.

There is only one node, that is v1, with an in-degree of 0 in the optimal persistent graph T, but it cannot act as the leader. Thus, T is further adjusted by SP-OPGAA as proposed earlier in this study, with the concrete process as shown in the following.

In T, the node v2 with an in-degree greater than 0 that can act as the leader is chosen and node v1 with an in-degree less than 2 is found so that there could be a path, , from v1 to v2. Then all the arcs on this path are reversed to obtain the adjusted optimal persistent graph, T, as shown in Fig. 8(a). Nevertheless, the in-degree of v2 in T is still greater than 0, which does not meet the leader constraint. Therefore, the above process needs to be repeated to find node v12 and reverse all the arcs on the path, , from v12 to v2 to obtain the adjusted optimal persistent graph, T, as shown in Fig. 8(b). As a result, the in-degree of v2 in T is 0, which meant T is the optimal persistent graph that satisfies the leader constraint, namely the optimal communication topology of this heterogeneous multi-agent persistent formation. acts as the leader of this formation, and the formation communication cost is 17714.

Fig. 8. (color online) Process for SP-OPGAA to generate the optimal persistent graph, T, that satisfies the leader constraint. (a) The optimal persistent graph, T, after reversing the arcs on the path, , from v1 to v2; (b) The optimal persistent graph, T, after reversing the arcs on the path, , from v12 to v2.
5. Conclusions

When heterogeneous multiple agents comprise a formation shape, not every agent can act as the leader. In view of this leader constraint, in this study we propose an algorithm to generate the optimal persistent formation for heterogeneous multi-agent systems. First, we generate an optimal persistent graph of the formation network topology by adding a virtual node and virtual arcs, generating and combining minimum cost arborescence, adding arcs, and reversing paths. Then, the optimal persistent graph is adjusted by using path reversal to satisfy the leader constraint. This algorithm supports the generation of the optimal persistent formation for any formation shape in 2D space under any leader constraint. For future research, further consideration will be given to communication failures that may occur in the process when the heterogeneous multi-agent formation keeps its formation shape. In addition, the dynamic optimization of persistent formation for leader-constrained heterogeneous multi-agent systems in the case of communication failure will be investigated.

Reference
[1] Barrientos A G Lopez J L Espinoza E S Hoyo J Valencia G 2016 IEEE Latin America Transactions 14 1184
[2] Guo H Chen S Bao A M Behrangi A Hong Y Ndayisaba F Hu J J Stepanian P M 2016 Atmos. Res. 176 121
[3] Nigam N Bieniawski S Kroo I Vian J 2012 IEEE T Control Syst 20 1236
[4] Cao X Zhu D Q Yang S X 2016 IEEE Transactions on Neural Networks and Learning Systems 27 2364
[5] Giulietti F Pollini L Innocenti M 2000 IEEE Control Systems 20 34
[6] Pollini L Giulietti F Innocenti M 2002 American Control Conference, May 8–10, 2002, Hilton Anchorage and Egan Convention Center Anchorage, Alaska, USA 2860
[7] Ren W 2007 IET Control Theory & Applications 1 505
[8] Yang H Jiang B Zhang Y M 2014 International Journal of Control Automation and Systems 12 29
[9] Hendrickx J M Fidan B Changbin Y Anderson B D O Blondel V D 2008 IEEE T Automat. Control 53 968
[10] Yu C Anderson B D O 2009 Int. J. Robust Nonlin. 19 1427
[11] Motevallian S A Yu C Anderson B D O 2015 Int. J. Robust Nonlin. 25 1654
[12] Tousi M M Khorasani K 2012 Automatica 48 410
[13] Tousi M M Khorasani K 2015 Int. J. Control 88 90
[14] Hendrickx J M Fidan B Yu C Anderson B D O Blondel V D 2006 the 17th International Symposium on Mathematical Theory of Networks and Systems (MTNS2006) July 24–28 Kyoto, Japan 859
[15] Smith B S Egerstedt M Howard A 2009 Mobile Networks & Applications 14 322
[16] Luo X Y Shao S K Zhang Y Y Li S B Guan X P Liu Z X 2014 Chin. Phys. 23 028901
[17] YLuo X Li S B Guan X P 2009 Chin. Phys. 18 3104
[18] Luo X Y Shao S K Guan X P Zhao Y J 2013 Acta Autom. Sin. 39 1431 (in Chinese)
[19] Luo X Y Yang F Li S B Guan X P 2014 Acta Autom. Sin. 40 1311 (in Chinese)
[20] Summers T H Yu C B Dasgupta S Anderson B D O 2011 IEEE T. Automat. Control 56 2772
[21] Gabow H N Galil Z Spencer T Tarjan R E 1986 Combinatorica 6 109
[22] Dijkstra E W 1959 Numerische Mathematics 1 269
[23] Ren R Zhang Y Y Luo X Y Li S B 2010 International Journal of Automation and Computing 7 557